This invention relates to the storage of information on computer-readable media such as disk drives, solid-state disk drives, and other data storage systems.
An example of a system storing information comprises a computer attached to a hard disk drive. The computer stores data on the hard disk drive. The data is organized as tables, each table comprising a sequence of records. For example, a payroll system might have a table of employees. Each record corresponds to a single employee and includes, for example,                1. First name (a character string),        2. Last name (a character string),        3. Social Security Number (a nine-digit integer),        4. A birth date (a date), and        5. An annual salary, in cents (a number).        
The system might maintain another table listing all of the payments that have been made to each employee. This table might include, for example,                1. Social Security Number,        2. Payroll date (a date), and        3. Gross pay (a number).        
The employee table might be maintained in sorted order according to social security number. By keeping the data sorted, the system may be able to find an employee quickly. For example, the data were not sorted then the system might have to search through every record to find an employee. If the data is kept sorted, on the other hand, then the system could find an employee by using a divide-and-conquer approach, in the same way that one can look up a phone number in a hardcopy phone book by dividing the book in two, and determining whether your party is in the first half or the second half, and then repeating this divide-and-conquer approach on the selected half.
The problem of efficiently maintaining sorted data can become more difficult when disk drives or other real data storage systems are used. Storage systems often have interesting performance properties. For example, having read a record from disk, it is typically much cheaper to read the next record than it is to read a record at the other end of the table. Many storage systems exhibit “locality” in which accessing a set of data that is stored near each other is cheaper than accessing data that distributed far and wide.
This invention can be used to maintain data, including but not limited to these sorted tables, as well as other uses where data needs to be organized in a computer system.